In many digital computing applications, it is necessary to identify the first "1" or the last "1" within a data word, or within a string of "1's" and "0's". For instance, it may be necessary in certain data processing applications to normalize the largest data value within a set of data values to a predetermined order of magnitude. After such a normalization the largest data value will have a one in the most significant bit. Generally this process may be accomplished by identifying the largest data word and then determining the position of the first bit containing a one, calculating the number of places between the leading one and the most significant bit and shifting the data word to the left a number of places equal to the calculated difference. Priority encoders are a class of digital circuits that identify the leading or trailing one in a data word.
Known priority encoders determine the leading one, for instance, by generating a carry signal at each bit position and propagating the signal from most significant bit to least significant bit. If any bit is a one, then its carry signal will block all lower order bits from generating a signal indicating a one at their corresponding bit position. The most significant bit will generate a carry signal if its data bit is a logic one. Every other bit will generate a carry signal if its data bit is a logic one or if the carry bit from the next most significant generated a carry signal. A priority encoder designed to determine the trailing one, will propagate the carry signal from least significant bit to most significant bit. In addition, the least significant bit will generate a carry signal if its corresponding data bit is a logic one.
Known priority encoders require a certain propagation time for their outputs to settle on a set of final correct values. A known priority encoder takes N inversion delays to propagate a signal through itself for an N bit data word, where N is an integer. Modern data processing systems regularly process data words of thirty-two, sixty-four and even one hundred and twenty-eight bit lengths. These bit lengths propagate through such a known priority encoder too slowly for many operating speeds.